package com.hyper_yang.algorithmRecord;

import java.util.ArrayDeque;

// 最大的矩形面积
public class LeetCode_84 {

    // 方法一: 暴力法(遍历所有可能的边界) Tn = O(n ^ 2) 超时
    public static int largestRectangleArea1(int[] heights) {
        // 定义变量保存的最大面积
        int largestArea = -1;
        // 遍历所有元素，作为矩阵左边界
        for (int left = 0; left < heights.length; left++) {
            // 保存当前矩形高度
            int currHeight = heights[left];
            // 选取右边界
            for (int right = left; right < heights.length; right++) {
                currHeight = Math.min(currHeight, heights[right]);
                int currArea = (right - left + 1) * currHeight;
                largestArea = Math.max(largestArea, currArea);
            }
        }
        return largestArea;
    }

    // 方法二: 双指针法(遍历所有可能的高度) Tn = O(n ^ 2) 超时
    public static int largestRectangleArea2(int[] heights) {
        int largestArea = -1;
        // 遍历所有元素，以每个柱子高度作为最终矩形的高度
        for (int i = 0; i < heights.length; i++) {
            // 保存当前的高度
            int currHeight = heights[i];
            // 定义左右指针
            int left = i, right = i;
            // 寻找左边界
            while (left >= 0) {
                if (heights[left] < currHeight) break;
                left--;
            }
            // 寻找右边界
            while (right < heights.length) {
                if (heights[right] < currHeight) break;
                right++;
            }
            // 计算当前高度
            int currArea = (right - left - 1) * currHeight;
            largestArea = Math.max(largestArea, currArea);
        }
        return largestArea;
    }

    // 方法三: 双指针法（改进） Tn = O(n) Sn = O(n) 通过
    public static int largestRectangleArea3(int[] heights) {
        // 定义变量保存最大面积
        int largestArea = -1;
        // 保存每个柱子对应的左右边界
        int n = heights.length;
        int[] lefts = new int[n];
        int[] rights = new int[n];
        // 遍历数组,寻找左边界
        for (int i = 0; i < n; i++) {
            // 保存当前的高度
            int currHeight = heights[i];
            // 定义左指针
            int left = i - 1;
            // 寻找左边界
            while (left >= 0) {
                if (heights[left] < currHeight) break; // 如果左边柱子更矮，那左边界就是左边柱子
                left = lefts[left]; // 如果左边柱子更高，就直接赋值左边柱子的左边界
            }
            lefts[i] = left;
        }
        // 遍历数组,寻找右边界
        for (int i = n - 1; i >= 0; i--) {
            // 保存当前的高度
            int currHeight = heights[i];
            // 定义右指针
            int right = i + 1;
            // 寻找右边界
            while (right < n) {
                if (heights[right] < currHeight) break; // 如果右边柱子更矮，那右边界就是右边柱子
                right = rights[right]; // 如果右边柱子更高，就直接赋值右边柱子的左右边界
            }
            rights[i] = right;
        }
        // 遍历所有元素，计算面积
        for (int i = 0; i < n; i++) {
            int currArea = (rights[i] - lefts[i] - 1) * heights[i];
            largestArea = Math.max(largestArea, currArea);
        }
        return largestArea;
    }

    // 方法四: 单调栈 Tn = O(n) Sn = O(n) 通过
    public static int largestRectangleArea4(int[] heights) {
        int largestArea = -1;
        // 保存左右边界
        int n = heights.length;
        int[] lefts = new int[n];
        int[] rights = new int[n];
        // 定义栈
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // 寻找左边界
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i])
                stack.pop();
            // 所有大于等于当前高度的元素全部弹出，就找到了左边界
            lefts[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        // 寻找右边界
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i])
                stack.pop();
            // 所有大于等于当前高度的元素全部弹出，就找到了右边界
            rights[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        // 计算面积
        for (int i = 0; i < n; i++) {
            int currArea = (rights[i] - lefts[i] - 1) * heights[i];
            largestArea = Math.max(largestArea, currArea);
        }

        return largestArea;
    }

    // 方法四: 单调栈(优化) 弹栈的时候确定右边界 Tn = O(n) Sn = O(n) 通过
    public static int largestRectangleArea(int[] heights) {
        int largestArea = -1;
        int n = heights.length;
        int[] lefts = new int[n];
        int[] rights = new int[n];
        // 初始化右哨兵为 n   【可能存在不 pop的情况】
        for (int i = 0; i < n; i++)
            rights[i] = n;

        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                rights[stack.peek()] = i;
                stack.pop();
            }
            lefts[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        for (int i = 0; i < n; i++) {
            int currArea = (rights[i] - lefts[i] - 1) * heights[i];
            largestArea = Math.max(largestArea, currArea);
        }
        return largestArea;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
        System.out.println(largestRectangleArea(new int[]{2, 4}));
    }
}
